package com.yoshino.leetcode.oneHundred.nineteenth;

class Solution {
    public int sumNums(int n) {
        //return n == 0 ? 0 : n + sumNums(n - 1);
        // 使用截断
        boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
        return n;
    }

    // 二叉搜索树
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        // 若在两侧则当前节点就是最小公共祖先
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor1(root.right, p, q);
        }
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor1(root.left, p, q);
        }
        return root;
    }

    // 二叉树
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null && right == null) {
            return null;
        }
        if (right == null) {
            return left;
        }
        if (left == null) {
            return right;
        }
        return root;
    }
}